#include "../tools.h"

/**
 * 序列 nums 可包含重复数字，求全排列
 * 
 * 输入：nums = [1,1,2]
 * 输出：
 * [[1,1,2],
 * [1,2,1],
 * [2,1,1]]
 * 
 * 使用标志位标记已访问
 */
class Solution {


public:
    void backtrack(vector<vector<int>> &res, vector<int>& path, const vector<int> &nums, vector<bool>& flag){
        if (path.size() == nums.size()){
            res.push_back(path);
            return;
        }
        
        for(int i = 0; i < nums.size(); ++i){
            if (flag[i]) continue;
            if (i > 0 && nums[i] == nums[i - 1] && !flag[i - 1]) continue;

            path.push_back(nums[i]);
            flag[i] = true;
            backtrack(res, path, nums, flag);
            path.pop_back();
            flag[i] = false;
        }
    }

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> res;
        if (nums.size() == 0) return res;

        vector<int> path;
        vector<bool> flag(nums.size(), false);
        sort(nums.begin(), nums.end());
        backtrack(res, path, nums, flag);
        return res;
    }
};


int main(int argc, char const *argv[])
{
    vector<int> nums = {1,1,2}; //[0,1,0,0,9]

    Solution s;

    auto res = s.permuteUnique(nums);
    show(res);

    
    return 0;
}
